package newcoder_exp.justPractise;
import java.util.*;
import org.junit.*;
public class NC28 {
    public class Solution {
        public String minWindow (String S, String T) {
            if (S.contains(T)) return T;
            int len = S.length();
            int lo = 0, hi, count = 0;
            String res = null;
            Map<Character, Integer> map = new HashMap<>();
            for (int i = 0; i < T.length(); i++) {
                char c = T.charAt(i);
                if (map.containsKey(c)) {
                    map.put(c, map.get(c) + 1);
                } else {
                    map.put(c, 1);
                }
                count++;
            }
            //lo移动到窗口开头
            while (lo < len && !map.containsKey(S.charAt(lo))) {
                lo++;
            }
            if (lo == len) return "";
            Deque<Character> deque = new LinkedList<>();
            StringBuilder sb = new StringBuilder();

            char c = S.charAt(lo);
            deque.offerLast(c);
            map.put(c, map.get(c) - 1);
            count--;
            hi = lo + 1;
            while (hi < len) {
                //lo移动到窗口开头
                while (!map.containsKey(S.charAt(lo))) {
                    lo++;
                    deque.pollFirst();
                }
                while (hi < len && count > 0) {
                    c = S.charAt(hi);
                    int cur;
                    if (deque.peekFirst() == c) {
                        deque.pollFirst();
                        c = S.charAt(lo);
                        lo++;
                        map.put(c, map.get(c) + 1);
                        count++;
                        while (!map.containsKey(S.charAt(lo))) {
                            lo++;
                            deque.pollFirst();
                        }
                    }
                    if (map.containsKey(c) && (cur = map.get(c)) > 0) {
                        map.put(c, cur - 1);
                        count--;
                    }
                    deque.offerLast(c);
                    hi++;
                } //此时，count值为0
                if (count == 0) { //防止是因为hi到达终点
                    if (res == null || res.length() > deque.size()) {
                        sb = new StringBuilder();
                        List<Character> list = new ArrayList<>(deque);
                        for (int i = 0; i < list.size(); i++) {
                            sb.append(list.get(i));
                        }
                        res = sb.toString();
                    }
                }

                //一轮考量结束，将lo回归到最适合的位置
                deque.pollFirst();
                c = S.charAt(lo);
                lo++;
                map.put(c, map.get(c) + 1);
                count++;
            }

            /* 
            
                S="XDOYEZODEYXNZ"
                T ="XYZ"T="XYZ"
            */
            return res;
        }
    } 


    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{};
        String res = s.minWindow("ab", "A");
        res = s.minWindow("a", "b");
        System.out.println(res);
    }
}
